package main

// 78. 子集
func main() {
	nums := []int{1, 2, 3}
	permuteNums := subsets(nums)

	for _, permuteNum := range permuteNums {
		for _, num := range permuteNum {
			print(num, ",")
		}
		println()
	}
}

func subsets(nums []int) (ans [][]int) {
	// 当前值有两种状态，1：包含在子集，2：不包含在子集
	numsLen := len(nums)
	var tempNums []int

	var dfs func(idx int)
	dfs = func(idx int) {
		if idx == numsLen {
			ans = append(ans, append([]int{}, tempNums...))
			return
		}
		tempNums = append(tempNums, nums[idx])
		dfs(idx + 1)
		tempNums = tempNums[:len(tempNums)-1]
		dfs(idx + 1)
	}

	dfs(0)

	return ans
}

func subsets2(nums []int) (ans [][]int) { // ？ 这是什么骚鸡吧操作
	n := len(nums)
	for mask := 0; mask < 1<<n; mask++ {
		set := []int{}
		for i, v := range nums {
			if mask>>i&1 > 0 {
				set = append(set, v)
			}
		}
		ans = append(ans, append([]int(nil), set...))
	}
	return
}

// 给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的
//子集
//（幂集）。
//
//解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
//
//
//
//示例 1：
//
//输入：nums = [1,2,3]
//输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
//示例 2：
//
//输入：nums = [0]
//输出：[[],[0]]
//
//
//提示：
//
//1 <= nums.length <= 10
//-10 <= nums[i] <= 10
//nums 中的所有元素 互不相同
